package com.buddy.learn.algorithm.simple;

/**
 *
 * n 代表 n个数 1,2,3,4,5,6,...,n
 * k 代表反转次数
 * 1,r 代表反转 1，r 之间的
 * 求： 反转 k 次之后的 1，r 区间的最终数组结果
 *
 * 比如: n = 7，则 链表为 1，2，3，4，5，6，7
 * 第一次反转：k = 1,r = 2 的结果为 2,1,3,4,5,6,7
 * 第二次反转：k = 2,r = 4 的结果为 4,3,1,2,5,6,7
 *
 * @author Buddy
 * @date 2021/4/21
 */
public class _反转链表2 {

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode ln_1 = new ListNode(1);
        ListNode ln_2 = new ListNode(2);
        ListNode ln_3 = new ListNode(3);
        ListNode ln_4 = new ListNode(4);
        ListNode ln_5 = new ListNode(5);
        ListNode ln_6 = new ListNode(6);
        ListNode ln_7 = new ListNode(7);
        head.next = ln_1;
        ln_1.next = ln_2;
        ln_2.next = ln_3;
        ln_3.next = ln_4;
        ln_4.next = ln_5;
        ln_5.next = ln_6;
        ln_6.next = ln_7;
        ln_7.next = null;

        ListNode result = reverseListNode(head, 3);

        while (result != null) {
            System.out.print(result.data + " ");
            result = result.next;
        }
    }

    /**
     * 反转链表
     *
     * @param head 头节点
     * @param r    翻转区间
     * @return 新的头节点
     */
    private static ListNode reverseListNode(ListNode head, int r) {
        if (head == null) {
            return null;
        }
        ListNode currNode = head;
        ListNode newNode = null;
        ListNode preNode = null;
        for (int i = 1; i <= r; i++) {
            ListNode next = currNode.next;
            if (i == r) {
                newNode = currNode;
                head.next = next;
            }
            currNode.next = preNode;
            preNode = currNode;
            currNode = next;
        }
        return newNode;
    }

    private static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }
}
